import java.util.ArrayList;
import java.util.List;

class Solution2 {
    public int m;
    public int n;
    public boolean[][] pac;
    public boolean[][] atl;
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        m=heights.length;
        n=heights[0].length;
        pac=new boolean[m][n];
        atl=new boolean[m][n];
        List<List<Integer>> list=new ArrayList<>();

        //x=0  太平洋
        for (int i = 0; i < n; i++) {
            if(!pac[0][i]){
                pac[0][i]=true;
                dfs1(0,i,heights);
            }
        }
        //y=0  太平洋
        for (int i = 0; i < m; i++) {
            if(!pac[i][0]){
                pac[i][0]=true;
                dfs1(i,0,heights);
            }
        }
        //x=m-1  大西洋
        for (int i = 0; i < n; i++) {
            if(!atl[m-1][i]){
                atl[m-1][i]=true;
                dfs2(m-1,i,heights);
            }
        }
        //y=n-1
        for (int i = 0; i < m; i++) {
            if(!atl[i][n-1]){
                atl[i][n-1]=true;
                dfs2(i,n-1,heights);
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(pac[i][j] && atl[i][j]){
                    List<Integer> t=new ArrayList<>();
                    t.add(i);
                    t.add(j);
                    list.add(new ArrayList<>(t));
                }
            }
        }

        return list;
    }

    public int[] dx={1,0,-1,0};
    public int[] dy={0,1,0,-1};
    //判断太平洋
    private void dfs1(int a, int b, int[][] heights) {
        for (int i = 0; i < 4; i++) {
            int x=dx[i]+a;
            int y=dy[i]+b;
            if(x>=0 && x<m && y>=0 && y<n && heights[a][b]<=heights[x][y] && !pac[x][y]){
                pac[x][y]=true;
                dfs1(x,y,heights);
            }
        }
    }
    //判断大西洋
    private void dfs2(int a, int b, int[][] heights) {
        for (int i = 0; i < 4; i++) {
            int x=dx[i]+a;
            int y=dy[i]+b;
            if(x>=0 && x<m && y>=0 && y<n && heights[a][b]<=heights[x][y] && !atl[x][y]){
                atl[x][y]=true;
                dfs2(x,y,heights);
            }
        }
    }
}